package com.veal98.stack_queue;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class SlidingWindowMaximum_239 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(); // 数组长度
        int k = sc.nextInt(); // 窗口大小
        int[] nums = new int[n];
        for (int i = 0; i < n; i ++) {
            nums[i] = sc.nextInt();
        }

        int[] res = maxSlidingWindow(nums, k);
        for (int num : res) {
            System.out.print(num + " ");
        }
    }

    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return new int[0];
        }

        // 存储最终结果
        int[] res = new int[nums.length - k + 1];
        // res 的下标
        int index = 0;


        // 单调递增的双端队列
        LinkedList<Integer> qmax = new LinkedList<>();

        for (int i = 0; i < nums.length; i ++) {
            // 1. 队列为空，直接入队
            if (qmax.isEmpty()) {
                qmax.addLast(i);
            }
            // 2. 当前元素 <= 队尾元素，直接入队
            else if (nums[i] <= nums[qmax.peekLast()]) {
                qmax.addLast(i);
            }
            // 3. 当前元素 > 队尾元素，则将队尾元素依次出队
            else {
                // 直到队尾元素 <= 当前元素
                while (!qmax.isEmpty() && nums[i] > nums[qmax.peekLast()]) {
                    qmax.pollLast();
                }
                // 再将当前元素从队尾入队
                qmax.addLast(i);
            }

            // 栈顶元素过期, 则将其出队
            if (qmax.peekFirst() == i - k) {
                qmax.pollFirst();
            }

            // 队头就是当前窗口的最大元素
            if (i >= k - 1) {
                res[index ++] = nums[qmax.peekFirst()];
            }
        }

        return res;
    }

}
